﻿// Black Box POJ - 1442 训练营.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>


/*
https://vjudge.net/problem/POJ-1442#author=GPT_zh
我们的黑匣子代表一个原始数据库。它可以保存一个整数数组，并且有一个特殊的 i 变量。在初始时刻，黑匣子是空的，i 等于 0。这个黑匣子处理一系列命令（交易）。有两种类型的交易：

ADD (x): 将元素 x 放入黑匣子；
GET: 将 i 增加 1，并输出黑匣子中包含的所有整数中的第 i 小的数。请记住，i-最小值是指在黑匣子元素按非递减排序后位于第 i 个位置的数。

让我们来看一个可能的 11 个交易的序列：

示例 1

N Transaction i Black Box contents after transaction Answer

      (elements are arranged by non-descending)

1 ADD(3)      0 3

2 GET         1 3                                    3

3 ADD(1)      1 1, 3

4 GET         2 1, 3                                 3

5 ADD(-4)     2 -4, 1, 3

6 ADD(2)      2 -4, 1, 2, 3

7 ADD(8)      2 -4, 1, 2, 3, 8

8 ADD(-1000)  2 -1000, -4, 1, 2, 3, 8

9 GET         3 -1000, -4, 1, 2, 3, 8                1

10 GET        4 -1000, -4, 1, 2, 3, 8                2

11 ADD(2)     4 -1000, -4, 1, 2, 2, 3, 8

需要设计一个高效的算法来处理给定的交易序列。ADD 和 GET 交易的最大数量：每种类型最多 30000 次。

让我们用两个整数数组描述交易序列：

1. A(1), A(2), ..., A(M): 正在包含在黑匣子中的元素序列。A 的值是绝对值不超过 2 000 000 000 的整数，M ≤ 30000。例如，对于示例，我们有 A=(3, 1, -4, 2, 8, -1000, 2)。

2. u(1), u(2), ..., u(N): 一个序列，设置在第一次、第二次，... 和第 N 次 GET 交易时包含在黑匣子中的元素数量。例如，对于示例，我们有 u=(1, 2, 6, 6)。

黑匣子算法假定自然数序列 u(1), u(2), ..., u(N) 按非递减顺序排序，N ≤ M，并且对于每个 p（1 ≤ p ≤ N），不等式 p ≤ u(p) ≤ M 是有效的。这是因为对于我们 u 序列的第 p 个元素，我们执行一个 GET 交易，从 A(1), A(2), ..., A(u(p)) 序列中给出第 p 小的数。

输入
输入按照给定顺序包含：M, N, A(1), A(2), ..., A(M), u(1), u(2), ..., u(N)。所有数字由空格和（或）换行符分隔。
输出
为给定的交易序列写出黑匣子的答案序列，每行一个数字。

7 4
3 1 -4 2 8 -1000 2
1 2 6 6

3
3
1
2

*/
int main()
{
    std::cout << "Hello World!\n";
}

 